//## begin module%3B94E40A026D.cm preserve=no
//	  %X% %Q% %Z% %W%
//## end module%3B94E40A026D.cm

//## begin module%3B94E40A026D.cp preserve=no
//	+----------------------------------------------+
//	| SVMBR - A program for training SVMs          |
//	+----------------------------------------------+
//	| * Creator, modeling, coding:                 |
//	|    Marcelo Barros de Almeida                 |
//	|    barros@smar.com.br                        |
//	|    http://litc.cpdee.ufmg.br/~barros/        |
//	| * Coding, improvements, bug fixes:           |
//	|    Bernardo Penna                            |
//	|    bprc@brfree.com.br                        |
//	+----------------------------------------------+
//
//	 Copyright(c) 2002 by Marcelo Barros de Almeida
//	                            All rights reserved
//
//	-[CVS]------------------------------------------
//	$Author$
//	$Date$
//	$Source$
//	$Name$
//	$Revision$
//	------------------------------------------------
//## end module%3B94E40A026D.cp

//## Module: cache%3B94E40A026D; Package body
//## Subsystem: <Top Level>
//## Source file: D:\textotese\svmbr\src\cache.cpp

//## begin module%3B94E40A026D.additionalIncludes preserve=no
//## end module%3B94E40A026D.additionalIncludes

//## begin module%3B94E40A026D.includes preserve=yes
//## end module%3B94E40A026D.includes

// cache
#include "cache.h"
//## begin module%3B94E40A026D.declarations preserve=no
//## end module%3B94E40A026D.declarations

//## begin module%3B94E40A026D.additionalDeclarations preserve=yes
#include "pqueue.h"
//## end module%3B94E40A026D.additionalDeclarations


// Class Cache 









Cache::Cache (Kernel* kernelp, Data* datap, INT sizev)
  //## begin Cache::Cache%999602356.hasinit preserve=no
  //## end Cache::Cache%999602356.hasinit
  //## begin Cache::Cache%999602356.initialization preserve=yes
  //## end Cache::Cache%999602356.initialization
{
  //## begin Cache::Cache%999602356.body preserve=yes

	INT i;

	kernel = kernelp;
	data   = datap;
	size   = sizev;

	try{
		cache     = new REAL* [size];
		allocated = new INT   [size];
		valid     = new INT   [size];
		hashTable = new INT   [data->getnumExamples()];
		freelist  = new PQueue(size);

	} 
	catch(...){
		cerr << "Error when allocating memory (Cache::Cache)." << endl;
		exit(1);
	}

	for(i = 0 ; i < size ; i++) {
		allocated[i] = FALSE;
		valid[i]     = FALSE;
		hashTable[i] = -1;
		freelist->add(-i,i);
	}

	INT dataSize = data->getnumExamples();
	for(i = size; i < dataSize; i++){
		hashTable[i] = -1;
	}

  //## end Cache::Cache%999602356.body
}


Cache::~Cache()
{
  //## begin Cache::~Cache%.body preserve=yes
	for(INT i = 0 ; i < size ; i++)
		if(allocated[i])
			delete cache[i];
	delete cache;
	delete allocated;
	delete valid;
	delete freelist;
  //## end Cache::~Cache%.body
}



//## Other Operations (implementation)
REAL * Cache::getKernelRow (INT ri)
{
  //## begin Cache::getKernelRow%999602353.body preserve=yes
	
	// REAL * Cache::getKernelRow (INT ri)

	// get cache index
	INT r = hashTable[ri];

	// if allocated and with valida data, return cached values ...
	if(allocated[r] && valid[r]) return cache[r];

	// if allocated but not valid, allocate and return
	if(allocated[r])
		goto fill_and_return;

	if(valid[r]){
		cerr << "Ooops ! Not allocated but valid ? ERROR ! (Cache::getKernelRow)" << endl;
		exit(1);
	}

	// ... otherwise allocate and fill

	try{
		cache[r] = new REAL [size];
	} 
	catch(...){
		cerr << "Error when allocating memory (Cache::getKernelRow)." << endl;
		exit(1);
	}

	allocated[r] = TRUE;

fill_and_return:

	// ... and fill cache.
	INT dataSize = data->getnumExamples();
	for(INT ci = 0; ci < dataSize ; ci++) {
		INT c = hashTable[ci];
		if(c != -1){
			if(valid[c])
				cache[r][c] =  cache[c][r];
			else
				cache[r][c] =  kernel->evalKernel(ri,ci);
		}
	}

	valid[r] = TRUE;
	return cache[r];
		
  //## end Cache::getKernelRow%999602353.body
}

REAL Cache::evalKernel (INT ri, INT ci)
{
  //## begin Cache::evalKernel%999602354.body preserve=yes

	// REAL Cache::evalKernel (INT ri, INT ci)

	// get cache indexes
	INT r = hashTable[ri];
	INT c = hashTable[ci];

	if((r == -1) || (c == -1))
		return kernel->evalKernel(ri,ci);

	// if allocated return cached value ...
	if(allocated[r] && valid[r])	return cache[r][c];
	if(allocated[c] && valid[c])	return cache[c][r];	

	// ... otherwise, allocate row and return the desired value.
	REAL* tmp = getKernelRow(ri);

	//kernel->evalKernel(ri,ci) != tmp[c])
	return tmp[c];
  //## end Cache::evalKernel%999602354.body
}

INT Cache::del (INT idx)
{
  //## begin Cache::del%1013528658.body preserve=yes

	INT i = hashTable[idx];

	if(i == -1)	return i;

	valid[i] = FALSE;
  hashTable[idx] = -1;
	freelist->add(-i,i);

  return i;

  //## end Cache::del%1013528658.body
}

VOID Cache::add (INT idx)
{
  //## begin Cache::add%1013528659.body preserve=yes

	if(freelist->getnumElements() == 0) {
		cerr << "Error: this condition should not happen ! Freelist empty !!! (Cache::add(idx))." << endl;
		exit(1);
	}

	INT p = freelist->remove(0);
	hashTable[idx] = p;
	valid[p] = FALSE;

  //## end Cache::add%1013528659.body
}

VOID Cache::SetChunk (INT *chunkSet)
{
  //## begin Cache::SetChunk%1013528660.body preserve=yes

	INT i;

#ifdef SVMBR_DBG
	INT j = 0, k = 0;;
	for(i = 0 ; i < size ; i++){
		k = chunkSet[i];
		if(hashTable[k] != -1)
			j++;
	}
	cout << "Cache hit rate is " << ((REAL)(100*j)/(REAL)size) << "%" << endl;
#endif

	INT dataSize = data->getnumExamples();
	for(i = 0 ; i < dataSize ; i++)
		del(i);

	for(i = 0 ; i < size ; i++)
		add(chunkSet[i]);


  //## end Cache::SetChunk%1013528660.body
}

VOID Cache::DontUseChunk ()
{
  //## begin Cache::DontUseChunk%1013528661.body preserve=yes
	INT ne = data->getnumExamples();
	INT i;

	if(size != ne) {
		cerr << "Error: this condition should not happen !!! (Cache::SetFullCache)." << endl;
		exit(1);
	}

	for(i = 0 ; i < ne ; i++)	del(i);
	for(i = 0 ; i < ne ; i++)	add(i);
  //## end Cache::DontUseChunk%1013528661.body
}

// Additional Declarations
  //## begin Cache%3B94DEC300F8.declarations preserve=yes
  //## end Cache%3B94DEC300F8.declarations

//## begin module%3B94E40A026D.epilog preserve=yes
//## end module%3B94E40A026D.epilog
